package Greedy.ks;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: LDeng
 * @Date: 2021-04-17 13:53
 */
public class Knapsack {

    public static void main(String[] args) {
        //价值主导
        select("价值主导",(Article a1,Article a2)->{
            return a2.value-a1.value;//从大到小排序
        });

        //重量主导
        select("重量主导",(Article a1,Article a2)->{
            return a1.weight-a2.weight;//从小到大排序
        });

        //价值密度主导
        select("价值密度主导",(Article a1,Article a2)->{
            return Double.compare(a2.ValueDensity,a1.ValueDensity);
        });
    }

    static void select(String title,Comparator<Article> cmp){
        Article[] articles = new Article[]{
                new Article(35, 10), new Article(30, 40),
                new Article(60, 30), new Article(50, 50),
                new Article(40, 35), new Article(10, 40),
                new Article(25, 30)
        };
        Arrays.sort(articles,cmp);

        int capacity=150;
        int weight=0;
        int value=0;
        List<Article> selectedArticles=new LinkedList<>();

        for (int i = 0; i < articles.length &&weight<capacity; i++) {
            int newWeight=weight+articles[i].weight;
            if(newWeight<=capacity){
                weight=newWeight;//更新总重量
                value+=articles[i].value;//更新总价值
                selectedArticles.add(articles[i]);//加入已选中的列表中
            }
        }
        System.out.println("-----"+title+"------");
        System.out.println("总价值："+value);
        System.out.println("总重量："+weight);
        for (int i = 0; i < selectedArticles.size(); i++) {
            System.out.println(selectedArticles.get(i));
        }
    }



}
